package com.learn.algorlthm;

/**
 * @classname:
 * @Description:二叉搜索树的第K个节点
 * @author: yfpu
 * @Date: 2018-08-14 17:48
 */
public class Learn54 {

    /**
     * 解题思路：
     * 利用二叉查找树中序遍历的特点
     */

    private TreeNode ret;
    private int cnt = 0;

    public TreeNode kthNode(TreeNode pRoot, int k) {
        inOrder(pRoot, k);
        return ret;
    }

    private void inOrder(TreeNode root, int k) {
        if (root== null || cnt > k )
            return;
        inOrder(root.left, k);

        cnt++;
        if (k == cnt)
            ret = root;

        inOrder(root.right, k);
    }


    static class TreeNode{
        public int value;

        public TreeNode left;
        public TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int value) {
            this.value = value;
        }
    }

}
